package com.example.SP20240516;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static int triangleNumber(int[] nums) {
        int ret = 0;
        for (int c = nums.length - 1; c >= 2; c--){
            int b = c - 1;
            int a = 0;
            while (a < b){
                if (nums[a] + nums[b] >= nums[c]){
                    ret += b - a;
                }else{
                    a++;
                }
            }
        }

        return ret;
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();

        for (int i = nums.length - 1; nums[i] >= 0; i--){
            int target = -nums[i];
            int left = 0;
            int right = i - 1;
            while (left < right){
                if(nums[left] + nums[right] < target){
                    left++;
                }else if (nums[left] + nums[right] > target){
                    right--;
                }else{
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],
                            nums[left], nums[right])));
                }
            }
        }

        return ret;
    }
    public static void main(String[] args) {
        threeSum(new int[]{-1, 0, 1, 2, -1, -4});
    }
}
